package leetcode_周赛._2022._202208;

import java.util.*;

/**
 * 305 场周赛
 *
 * @author yzh
 * @version 1.0
 * @date 2022/8/7 11:13
 */
public class _07 {

    /**
     * 6136. 算术三元组的数目
     * 哈希表、三指针
     *
     * @param nums
     * @param diff
     * @return
     */
    public int arithmeticTriplets_Set(int[] nums, int diff) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (set.contains(num - diff) && set.contains(num - 2 * diff)) ++ans;
            set.add(num);
        }
        return ans;
    }

    public int arithmeticTriplets_ThreePoint(int[] nums, int diff) {
        int ans = 0;
        for (int i = 0, j = 1, k = 2; k < nums.length; k++) {
            while (nums[j] + diff < nums[k]) ++j;
            if (nums[j] + diff > nums[k]) continue;
            while (nums[i] + diff * 2 < nums[k]) ++i;
            if (nums[i] + diff * 2 == nums[k]) ++ans;
        }
        return ans;
    }


    /**
     * 6139. 受限条件下可到达节点的数目
     *
     * @param n
     * @param edges
     * @param restricted
     * @return
     */
    public int reachableNodes(int n, int[][] edges, int[] restricted) {
        List<Integer>[] adj = new List[n];
        for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
        for (int[] edge : edges) {
            adj[edge[0]].add(edge[1]);
            adj[edge[1]].add(edge[0]);
        }
        boolean[] visited = new boolean[n];
        for (int restrict : restricted) visited[restrict] = true;
        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(0);
        int ans = 0;
        while (!queue.isEmpty()) {
            int node = queue.poll();
            visited[node] = true;
            List<Integer> list = adj[node];
            for (int num : list) {
                if (visited[num]) continue;
                queue.offer(num);
            }
            ++ans;
        }
        return ans;
    }


    /**
     * 6137. 检查数组是否存在有效划分
     * 动态规划
     * dp[i]: 表示 0 到 i 之间的元素是否能够有效划分
     * 当想要凑两个元素时, [0, i - 2] 必须是有效划分, 再判断 [i - 1, i] 是否是有效划分
     * 当想要凑三个元素时, [0, i - 3] 必须是有效划分, 再判断 [i - 2, i - 1, i] 是否是有效划分
     *
     * @param nums
     * @return
     */
    public boolean validPartition(int[] nums) {
        int n = nums.length;
        if (n == 2) return nums[0] == nums[1];
        boolean[] dp = new boolean[n];
        dp[1] = nums[0] == nums[1];
        dp[2] = (nums[0] == nums[1] && nums[0] == nums[2]) || (nums[2] == nums[0] + 2 && nums[2] == nums[1] + 1);
        for (int i = 3; i < n; i++) {
            if (dp[i - 2] && nums[i] == nums[i - 1]) dp[i] = true;
            else if (dp[i - 3] && nums[i] == nums[i - 1] && nums[i] == nums[i - 2]) dp[i] = true;
            else if (dp[i - 3] && nums[i] == nums[i - 1] + 1 && nums[i] == nums[i - 2] + 2) dp[i] = true;
        }
        return dp[n - 1];
    }

    public boolean validPartition_Brevity(int[] nums) {
        int n = nums.length;
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 2; i <= n; i++)
            if (dp[i - 2] && nums[i - 1] == nums[i - 2] ||
                    i > 2 && dp[i - 3] && (nums[i - 1] == nums[i - 2] && nums[i - 1] == nums[i - 3] ||
                            nums[i - 1] == nums[i - 2] + 1 && nums[i - 1] == nums[i - 3] + 2)) dp[i] = true;
        return dp[n];
    }

}
